Historically, when a company or any other group of people needed to have their computers and the like “networked” together they would contact a local telephone company or another so-called “service provider” (“SP”) to assist them. The service provider would design and construct a network using so-called “connection-oriented” technology (e.g., some combination of leased “private lines” and the publicly switched telephone network, dial-up lines or the like).
As is known by those skilled in the art, networks designed using existing connection-oriented technologies have their drawbacks.
In order to overcome the drawbacks inherent in existing network designs, SP based, Internet-protocol (“IP”) virtual private networks (“VPNs”) have been developed (“IP-VPNs” for short). IP-VPNs are designed using “connectionless” technology. One of the advantages a connectionless network has over a connection-oriented network is that there is no need for an administrator or the like of a network to specify traffic characteristics between two sites or locations (hereafter collectively referred to as “location(s)”) in a network. Instead, it is now up to the SP to deliver communication services that are associated with a certain “Quality of Service” (“QoS”) level. However, this does allow an SP to manage all of the traffic flowing from each of its customers as an aggregate, resulting in increased efficiencies in both network resource usage and network management.
Two common techniques used to create an SP based, IP-VPN are Multi-Protocol Label Switching (“MPLS”) and “virtual routers” (“VR”). It should be understood that both techniques are used to implement VPNs. The MPLS approach is articulated in an Internet protocol proposal Request for Comment (“RFC”) 2547 (RFC 2547) entitled “BGP/MPLS VPN'S” (as well as in internet draft-rfc2547bis, its second version). The VR approach is in actuality, a family of techniques. Therefore there are a number of possible ways to implement a VR-based, VPN. One implementation is articulated in Internet RFC 2917 entitled “A Core MPLS IP VPN Architecture”. 
Overly simplified, the difference between an MPLS-VPN and a VR-VPN is that the former uses so-called route distinguishers (RDs) and route targets (RTs) to route communications traffic (e.g., data) from one location in a network to another, while the latter uses so-called “access lists” to accomplish the same thing.
Before discussing the details of the present invention, it may be helpful to introduce some terms which will be used repeatedly throughout the discussion below.
In RFC 2547 (i.e., MPLS-based techniques), an IP network is divided into two tiers, a core network that consists of “core routers”, and edge networks that consist of “service provider edge” (“PE”) routers. Customer routers are in turn connected to the PE routers. The customer routers that are directly attached to the PE routers are referred to as “customer edge” (“CE”) routers. All VPN functions are implemented in the PE routers. Core routers are operable to forward MPLS “packets”, (e.g., small bits of data) but they are not assigned VPN tasks. Similarly, CE routers behave as if they are connected to ordinary routers, (e.g., they do not receive information telling them that PE routers are RFC 4547 compliant).
In RFC 2547, a customer location is connected to a PE router through a CE router and the connection is identified via a layer 1 or a layer 2 identifier that can represent: a physical interface ID; a virtual path/virtual circuit identifier of an ATM interface (“ATM” stands for Asynchronous Transfer Mode); a data link connection identifier of a frame relay interface; a virtual local area network identifier of an Ethernet serial link interface; and/or the MPLS label of a MPLS interface. One or more of these interfaces will be referred to hereafter as a “pathway”.
A basic requirement for a VPN is that each IP VPN subscriber must be able to use its own private IP addressing scheme. Therefore, each PE router needs to be able to route IP packets based on differing incoming data streams. In theory, this may require a different decision process for each data stream. There are two possible approaches which can be used by a PE router. The first is to create a “routing/forwarding table” for each VPN. The second is to create a single routing/forwarding table with “context” for each VPN. In RFC 2547, the first approach is considered resource and management intensive, so the second approach is utilized.
Routing tables are stored within each PE router. It is the routing tables that contain the instructions, guidelines and the like which tells the PE router how to treat each received data stream. That is to say, each routing table provides directions, for example, on how to handle an incoming data stream, where to route it next, if any action should be taken at all, etc. . . .
The context specific table for each VPN is referred to as a VPN Routing and Forwarding (“VRF”) table. Each VRF table is identified by a parameter known as a Route Distinguisher (“RD”). For the sake of efficiency, multiple data streams from different pathways can point to the same VRF. An RD contains two fields that identify the SP and the routing domain within the SP's network. RD assignment is the responsibility of the SP.
To create such VRF tables manually is cost prohibitive and not scaleable. Therefore, a “routing protocol” between PE routers is used to automatically update and synchronize the content of the VRF tables each time locations in the network are added, deleted or modified. In RFC 2547, the routing protocol used is a Border Gateway Protocol with Multi-Protocol Extensions (“BGP-MP”), as specified in RFC 2858 from the Internet Engineering Task Force.
The BGP-MP routing protocol specifies a number of parameters, one of which is called a Route Target (“RT”). A PE uses RTs to “advertise” its routes to other PEs that are considered its “peers”. RTs are used to describe the VPN (or “VPN” component) that the route is applicable to. Because a location may belong to multiple VPNs or VPN components, multiple RTs can be associated with a single route.
Both RDs and RTs are known as network wide parameters because they have to be unique across the entire network. To ensure that a VPN is working properly, RDs and RTs must be properly generated and assigned. If the incorrect RT is assigned it may be impossible for one or more PE routers to correctly route packets of data. Furthermore, if RDs are efficiently assigned the number of VRFs in a PE can be reduced, thereby allowing network resources to be conserved. Further still, with efficient RT assignment, it would be unnecessary to reconfigure existing PE routers each time a new location is added resulting in a considerable savings in network management.
RD and RT assignments will change over time because: (1) the networks they are associated with will change as new locations are added, deleted or modified; within such networks; and/or (2) the rules governing the flow of data to and from such locations will change.
There is, therefore, a need in the art for techniques which provide for the proper assignment of RDs and RTs.
In the discussion just concluded we focused on MPLS based techniques for routing data from one VPN to another. As stated earlier, there exists a second technique, the VR approach. We now turn our attention to that technique.
The VR technique involves the generation and use of a number of logical routers (i.e., software, firmware configured to carry out the functions and features of one or more physical routers . . . this technique is sometimes called “emulating” a physical router . . . ). Each logical router is adapted to exhibit the behavioral characteristics of separate physical routers. These logical routers are aptly referred to as virtual routers (“VRs”). In an IP-based VPN, each VPN is assigned a VR within each PE router. The VRs can be connected to each other via a core network and a number of layer 2/layer 3 technologies, such as ATM virtual connections, frame relay connections, IP encapsulation and Layer 2 Tunnel Protocol.
Sometimes, an SP's customer places restrictions on locations in its network (e.g., not all locations are allowed to communicate with each other directly). Because of this, a VR must be able to “filter” packets. That is to say, a VR must be able to, for example, determine whether to forward or discard a packet. The filtering capabilities of VRs are specific to the configuration of each VPN. Most VRs filter packets using at least the fields containing the IP source address, IP destination address, source and destination ports, protocol type and the type of service (“TOS”) byte embedded within each packet.
More specifically, each VR is linked or otherwise has access to, one or more “access list(s)”. These lists contain the exact instructions on how a VR should treat a received packet.
An access list usually comprises a number of entries or “statements”, each of which defines whether a particular packet will be forwarded or dropped based on whether the particular packet satisfies certain criteria. For example, an access list can specify that only packets with particular destination addresses are forwarded, while all others are discarded.
Access lists are assigned to a particular pathway (i.e., a particular interfacer which connects a PE and CE router) in a particular order. In general, for an incoming packet a VR is adapted to match the data packet with criteria specified in a first entry of a first access list. If a match is found, an action specified in the entry will be executed. If a match is not found, the VR is adapted to proceed to the next entry in the access list until a match is found or until the end of the list is reached.
There are two access lists, one transmission and one reception, associated with each pathway. These access lists are stored in PE routers. These two access lists are referred to as “master access lists” or “master lists”. Each master list, in turn, comprises a number of sub-access lists. When a new VPN or VPN component is added or deleted, a sub-access list has to be added or deleted from a master access list. In addition, when changes are made to an existing VPN or VPN component (e.g., modifying or removing a location), entries in the corresponding sub-access access lists have to be changed manually. This is labor intensive and leads to many mistakes.
Therefore, there is a need in the art for techniques which provide for the automatic generation and assignment of correct VR access lists automatically.
In general, there is a need in the art for methods and systems for configuring IP-based, VPNs as the VPNs change over time.